package com.origin.niuke.dynamic;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/18 19:53
 * 编辑距离(二)
 * 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，
 * 请输出将str1编辑成str2的最小代价。
 * 算法：动态规划
 * dp[i][j]: str1 的前 i 个字符串与 str2 的前 i 个字符串相等的代价
 * str1[i] == str2[j] -- dp[i][j] = dp[i - 1][j - 1]
 * str1[i] != str2[j] -- dp[i][j] = min(dp[i][j - 1] + 5, dp[i - 1][j] + 3, dp[i - 1][j - 1] + 2)
 * 注意：是操作 str1
 */
public class NC35 {

    public int minEditCost(String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int n = str1.length(), m = str2.length();
        if (n == 0) return dc * m;
        if (m == 0) return dc * n;
        int[][] dp = new int[n + 1][m + 1];
        // str1 为 "" 时, 在 "" 后面添加字符, 将 str1 编辑成 str2
        for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + ic;
        // 当 str2 为 "" 时, 删除 str1 的字符, 将 str1 编辑成 str2
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + dc;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j - 1] + rc, Math.min(dp[i][j - 1] + ic, dp[i - 1][j] + dc));
            }
        }
        return dp[n][m];
    }

    public int minEditCost_perfect(String str1, String str2, int ic, int dc, int rc) {
        int n = str1.length(), m = str2.length();
        if (n == 0 && m == 0) return 0;
        int[] dp = new int[m + 1];
        for (int i = 1; i <= m; i++) dp[i] = dp[i - 1] + ic;
        for (int i = 0; i < n; i++) {
            // dp[i][j] 与 dp[i - 1][j - 1] 和 dp[i - 1][j] 有关, 这里需要将 dp[i - 1][j - 1] 保存起来
            int pre = dp[0];
            for (int j = 1; j <= m; j++) {
                int tmp = dp[j];
                if (str1.charAt(i) == str2.charAt(j - 1)) dp[j] = pre;
                else dp[j] = Math.min(pre + rc, Math.min(dp[j - 1] + ic, dp[j] + dc));
                pre = tmp;
            }
        }
        return dp[m];
    }

}
